import java.util.AbstractList;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
import java.util.Date;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

public class Search {

	static int maxIterations = 200;

    public static List<Move> search(Board b, GameState gs) {
        for (int i = minMatchingDelta(Integer.MAX_VALUE, b, gs); i < maxIterations; i++) {
            LinkedList<Move> solution = new LinkedList<Move>();
            HashMap<GameState, Integer> seen = new HashMap<GameState, Integer>();
            seen.put(gs, i);

            boolean res = iddps(b, gs, i, solution, seen);
            if (res) {
				U.pr("Iterations: " + i);
                U.pr(seen.size());
                return solution;
            }
        }
        // We fail
		U.pr("Iterations maxed");
        return null;
    }
	
    /* Experimental. Does not work... */
    public static List<Move> IDA_search(Board b, GameState gs) {
//        int cost_limit = heuristics(b, gs);
//        int cost_limit = minMatching(maxIter, b, gs); ////// VIKTIGT!!! dfs() måste kunna nå ett block på max cost_limit drag, (tror jag), jämför C3 och C4
        int cost_limit = minMatching2(maxIter, b, gs);
//        int cost_limit = 200;
        while (true) {
            LinkedList<Move> solution = new LinkedList<Move>();
            HashMap<GameState, Integer> seen = new HashMap<GameState, Integer>();
            seen.put(gs, cost_limit);

            boolean[] res = new boolean[1];
            cost_limit = dfs(0, cost_limit, b, gs, res, solution, seen, cost_limit/2);
            if (res[0]) {
//                U.pr("1Cost: " + cost_limit);
                return solution;
            }
            if (cost_limit >= maxIter) {// (cost_limit >= maxIter+1) detta villkor är ALLTID falskt! får inte ha +1...
                // We fail
//                U.pr("2Cost maxed, cost_limit: "+cost_limit);
                maxIter = maxIter * 2;
            } else {
//                U.pr("3Cost: " + cost_limit);
            }
        }

//		LinkedList<Move> solution = new LinkedList<Move>();
//        HashMap<GameState, Integer> seen = new HashMap<GameState, Integer>();
//		boolean res = iddps(b, gs, 20, solution, seen, null);
//		return null;
    }
    
    ArrayList<Date> timer = new ArrayList<Date>();
    ArrayList<Long> totalTime = new ArrayList<Long>();
    
	void timer(boolean start, int i){
		if(i < timer.size()){
			if(start){
				timer.set(i, new Date());
			}else{
//				U.pr("time: "+timer.get(i).getTime());
				totalTime.set(i, totalTime.get(i) + 1 + (new Date().getTime() - timer.get(i).getTime()));
			}
		}else if(start){
			for(int n = timer.size(); n <= i; n++){
				timer.add(new Date());
				totalTime.add(new Long(0));
			}
		}
	}
	void prTime(){
		for(int i = 0; i < timer.size(); i++){
			U.pr("Time "+i+": "+totalTime.get(i));
		}
	}

	// TODO skicka in depth i pathFromTo() och från equals() i GS?
    public static int heuristics(Board b, GameState gs, int depth, int count) {
		if(count > 0){
			return 0;
		}else{
//			return 0;
//			return testStop(b, gs);
			return minMatchingDelta(depth, b, gs);
//	        return minMatching(depth, b, gs);
//	        return minMatching2(depth, b, gs);
		}
    }

	static int maxIter = 200;

    private static int dfs(int start_cost, int cost_limit, final Board b, GameState gs, boolean[] solved, List<Move> solution, HashMap<GameState, Integer> seen, int heuristicsCount) {
//		pr("start_cost: "+start_cost+"	cost_limit: "+cost_limit);
		int h = heuristics(b, gs, cost_limit, heuristicsCount);
		int thisH = h>0?heuristicsCount:(h/2);
        int min_cost = start_cost + h;
        if (min_cost > cost_limit) {
            return min_cost;
        }
        if (gs.isSolved(b)) {
            solved[0] = true;
            return cost_limit;
        }
        int next_cost_limit = maxIter;
        
		List<List<Move>> moves = Move.findAllPossibleMoves(b, gs, cost_limit);
        List<GameState> newStates = new ArrayList<GameState>();
        HashMap<GameState, List<Move>> lookup = new HashMap<GameState, List<Move>>();
        
		for(int i = 0; i < moves.size(); i++){
//			pr("HERE 1");
			List<Move> actions = moves.get(i);

			GameState tmpClone = new GameState(gs);
			for(int n = 0; n < actions.size(); n++){
				tmpClone.doMove(b, actions.get(n));
			}

			Integer seenDepth = seen.get(tmpClone);
			if (seenDepth == null || seenDepth < cost_limit - actions.size()-1) {
				newStates.add(tmpClone);
				lookup.put(tmpClone, actions);
				seen.put(tmpClone, cost_limit - actions.size()-1);

				int new_start_cost = start_cost + lookup.get(tmpClone).size();
				boolean[] s = new boolean[1];
				int new_cost_limit = dfs(new_start_cost, cost_limit, b, tmpClone, s, solution, seen, thisH-actions.size());
				if (s[0] != false) {
					solved[0] = true;
					addStatesToSolutionArray(solution, lookup.get(tmpClone));
					return new_cost_limit;
				}
				next_cost_limit = Math.min(next_cost_limit, new_cost_limit);
			}
		}

//        for (int i = 0; i < newStates.size(); i++) {
//            GameState state = newStates.get(i);
//
//            int new_start_cost = start_cost + lookup.get(state).size();
//            boolean[] s = new boolean[1];
//            int new_cost_limit = dfs(new_start_cost, cost_limit, b, state, s, solution, seen);
//            if (s[0] != false) {
//                solved[0] = true;
//				addStatesToSolutionArray(solution, lookup.get(state));
//                return new_cost_limit;
//            }
//            next_cost_limit = Math.min(next_cost_limit, new_cost_limit);
//        }
//		pr("HERE 9");
        return next_cost_limit;
    }  

    private static boolean iddps(final Board b, GameState gs, int depth, List<Move> solution, HashMap<GameState, Integer> seen) {
//		U.pr("depth: "+depth);
        // Search limit reached
        if (depth <= 0) {
//             U.pr("deep limit");
            return false;
        }
        // Goal state reached
        if (gs.isSolved(b)) {
            return true;
        }

//        List<Move> moves = Move.findAllPossibleMoves(b, gs, lastMove);
		List<List<Move>> moves = Move.findAllPossibleMoves(b, gs, depth);
        List<GameState> newStates = new ArrayList<GameState>();
//        HashMap<GameState, Move> lookup = new HashMap<GameState, Move>();
        HashMap<GameState, List<Move>> lookup = new HashMap<GameState, List<Move>>();
        
        // U.prB(U.boardToFlatString(b, gs, false));
        
//         for (int i = 0; i < moves.size(); i++) {
//            Move action = moves.get(i);
//
//			GameState tmpClone = new GameState(gs);
//            GameState newState = tmpClone.doMove(b, action);
//
//            // U.whatAmI_Move(action);
//
//            Integer seenDepth = seen.get(newState);
//            if (seenDepth == null || seenDepth < depth) {
//                newStates.add(newState);
//                lookup.put(newState, action);
//
//                seen.put(newState, depth);
//            }
//        }
//		for(int i = 0; i < moves.size(); i++){
////			Move action = moves.get(i).get(moves.get(i).size()-1);
//			List<Move> actions = moves.get(i);
//
//			GameState tmpClone = new GameState(gs);
////			U.pr("");
//			for(int n = 0; n < actions.size(); n++){
//				tmpClone.doMove(b, actions.get(n));
//			}
//
//			Integer seenDepth = seen.get(tmpClone);
//			if (seenDepth == null || seenDepth < depth - actions.size()-1) {
//				newStates.add(tmpClone);
//				lookup.put(tmpClone, actions);
//				seen.put(tmpClone, depth - actions.size()-1);
////				U.prBoardSet(moves.get(i), "########|#      #|#  $# .#|#.  $$.#|####   #|   #@ ##|   ####", false, 8);
//			}
////			U.pr("i"+i);
////			U.pr(moves.get(i), "#########|#    $. #|#    $. #|#    $. #|#  @    #|#########", false);
//		}

		for(int i = 0; i < moves.size(); i++){
//			Move action = moves.get(i).get(moves.get(i).size()-1);
			List<Move> actions = moves.get(i);

			GameState tmpClone = new GameState(gs);
//			U.pr("");
			for(int n = 0; n < actions.size(); n++){
				tmpClone.doMove(b, actions.get(n));
			}

			Integer seenDepth = seen.get(tmpClone);
			if (seenDepth == null || seenDepth < depth - actions.size()-1) {
				newStates.add(tmpClone);
				lookup.put(tmpClone, actions);
				seen.put(tmpClone, depth - actions.size()-1);
//				U.prBoardSet(moves.get(i), "########|#      #|#  $# .#|#.  $$.#|####   #|   #@ ##|   ####", false, 8);
			}
//			U.pr("i"+i);
//			U.pr(moves.get(i), "#########|#    $. #|#    $. #|#    $. #|#  @    #|#########", false);
		}
        
        // try {
            // System.in.read();
        // } catch (Exception e) {
        // }
        
        for (int i = 0; i < newStates.size(); i++) {
            GameState state = newStates.get(i);

//            if(!testStop(depth, b, state)){
				if(minMatching(depth, b, state) < depth){// TODO gör klart minMatching(), så att den kan ersätta testStop().
//			if(minMatchingDelta(depth, b, state) <= depth){
//					boolean res = iddps(b, state, depth - lookup.get(state).size(), solution, seen, lookup.get(state).get(lookup.get(state).size()-1));
					boolean res = iddps(b, state, depth - lookup.get(state).size(), solution, seen);
					if (res == true) {
	//                    solution.add(0, lookup.get(state).get(lookup.get(state).size()-1));
						addStatesToSolutionArray(solution, lookup.get(state));
						return true;
					}
			}
//				}
//            }
        }

        // Dead end
        return false;
    }

	// OBS this adds the solutions backwards!
	static void addStatesToSolutionArray(List<Move> solution, List<Move> stateArray){
		for(int i = stateArray.size()-1; i >= 0; i--){
			solution.add(0, stateArray.get(i));
		}
	}

	static int testStop(Board b, GameState gs){
		int blocksOnGoal = gs.blocksOnGoal(b);
		int blocks = gs.gs.length-1;
		return ((blocks - blocksOnGoal)*2 - 1);
	}

	static boolean testStop(int depth, Board b, GameState gs){
		int blocksOnGoal = gs.blocksOnGoal(b);
		int blocks = gs.gs.length-1;

//		if(gs.gs.length <= 2){
			if(((blocks - blocksOnGoal)*2 - 1) - depth > 0)
				return true;
			return false;
//		}

		
//		int max = 0;
//		for(int i = 0; i < gs.gs.length; i++){
//			if(gs.isBlock(gs.gs[i])){
//				if(!gs.isBlockAtGoal(b, gs, gs.getBlockPos(i))){
//					GameState G = new GameState();
//					G.gs = new byte[2];
//					G.pos = new int[2][2];
//					G.indexPlayer = 0;
//					G.gs[0] = gs.gs[gs.indexPlayer];
//					G.gs[1] = gs.getBlock(i);
//					G.pos[0] = gs.getPlayerPos();
//					G.pos[1] = gs.getBlockPos(i);
//					List<Move> moves = search(b, G);
//					if(moves != null)
////					max = Math.max(max, moves.size());
//					max += moves.size();
//				}
//			}
//		}
//		if(max - depth >= 0)// dead lock
//			return true;
//		return false;
	}

	static int minMatchingDelta(int depth, Board b, GameState gs){
//		int blocksOnGoal = gs.blocksOnGoal(b);
//		int blocks = gs.gs.length-1;
//			if(((blocks - blocksOnGoal)*2 - 1) - depth > 0)
//				return true;
		int val = 0;
		for(int i = 0; i < gs.gs.length; i++){
			if(GameState.isBlock(gs.gs[i]) && !GameState.isBlockAtGoal(b, gs, gs.pos[i])){
				int min = Integer.MAX_VALUE;
				for(int j = 0; j < b.goals; j++){
					int dx = Math.abs(gs.pos[i][0] - b.goalPos[j][0]);
					int dy = Math.abs(gs.pos[i][1] - b.goalPos[j][1]);
					if((dx+dy > 0)&&(dx+dy < min)){
						min = dx+dy;
//						pr("dx+dy: "+min);
					}
				}
				if(min > depth || (val+min) > depth){
					return Integer.MAX_VALUE;
				}else{
					val += min;
//					pr(val);
				}
			}
		}
//		pr("val: "+val);
		return val;
	}

	static int minMatching(int depth, Board b, GameState g){
		// För alla distToGoals måste det Existera en lösning på mål x sådan att det för alla andra distToGoals Existerar en lösning på mål y så y != x
		int[][] blocks = g.getBlockPoses();
		int[][] distToGoals = new int[blocks.length][b.goals];
//		pr("\n\ndistToGoals:");
		for(int i = 0; i < distToGoals.length; i++){
//			pr("\n\n");
//			pr("block[i][0]: "+blocks[i][0]);
//			pr("block[i][1]: "+blocks[i][1]);
			goalIn(distToGoals[i], depth, b, g, blocks[i], U.matrixClone(b.availableFligths2D));
//			pr("\n");
//			pr(distToGoals[i]);
		}
		int lowest = findLowestDiagonal(distToGoals, depth);

		int max = 0;
		for(int i = 0; i < blocks.length; i++){
			int dist = U.distFromTo(b, g, blocks[i], g.getPlayerPos(), depth);
			if(dist > max){
				max = dist;
			}
		}
//		pr("lowest "+lowest+"\n");

//		pr("lowest: "+lowest);
		return lowest+max;
	}

	static int minMatching2(int depth, Board b, GameState g){
		return minIter(depth, b, g, 0, g.getPlayerPos(), g.getBlockPoses(), b.goalPos);// TODO blocks! inte blocks^blocks
	}

	static int minIter(int depth, Board b, GameState g, int iter, int[] lastPos, int[][] blocks, int[][] goals){
		int min = depth;
//		pr("depth: "+depth+"	iter: "+iter);
//		int[][] blocks = g.getBlockPoses();
		if(iter > blocks.length){
			return 0;
		}
		for(int i = 0; i < blocks.length; i++){// TODO to goal
//			int[][] avalibeBlocks = allExcept(blocks, i);
			DistNodeAStar player = U.distNodeFromTo(b, g, lastPos, blocks[i], depth); // OBS - 1?
			if(player != null && player.moves >= 0){
				for(int n = 0; n < goals.length; n++){
//					int[][] avalibleGoals = allExcept(goals, n);
//					pr("dist: "+player.moves);
					DistNodeAStar goal = U.distNodeFromTo(b, g, player.pos, goals[n], depth);
					if(goal != null && goal.moves >= 0){
						int val = player.moves + goal.moves + minIter(depth, b, g, iter+1, player.pos, allExcept(blocks, i), allExcept(goals, n));
//						pr("val: "+val);
						if(min > val){
							min = val;
						}
					}
				}
			}
		}
//		pr("min: "+min);
		return min;
	}

	static int[][] allExcept(int[][] blocks, int exception){
		int[][] b = new int[blocks.length-1][2];
		int count = 0;
		for(int i = 0; i < blocks.length; i++){
			if(i != exception){
				b[count] = blocks[i];
				count++;
			}
		}
		return b;
	}

//	static int iter(int depth, Board b, GameState g, )

	static int findLowestDiagonal(int[][] matrix, int maxDepth){
//		return fLDI(matrix, new int[matrix.length], 0);
		return fLDI2(matrix, 0, new boolean[matrix.length], 0, maxDepth);
	}

	static int fLDI2(int[][] m, int p, boolean[] lockedCols, int y, int maxDepth){
		int min = maxDepth;
		for(int x = 0; x < m.length; x++){
//				pr("x: "+x+"	y: "+y);
			if(!lockedCols[x]){
//				pr("i: "+(int)(p+m[x][y])+"\n");
				if((p+m[x][y]) <= maxDepth){
					if(y == m[0].length-1){
						if(min > p+m[x][y]){
							min = p+m[x][y];
						}
					}else{// iter
						boolean[] lc = lockedCols.clone();
						lc[x] = true;
						int iter = fLDI2(m, p+m[x][y], lc, y+1, maxDepth);
						if(min > iter){
							min = iter;
						}
					}
				}else{
					return p+m[x][y];
				}
			}
		}
		return min;
	}

	static int fLDI(int[][] m, int[] indexes, int y){
		int min = Integer.MAX_VALUE;
		if(y < m.length-1){
			for(int i = 0; i < m[y].length; i++){
				if(!isInSet(indexes, i)){
					int[] c = indexes.clone();
					c[y] = i;
					int val = fLDI(m, c, y+1);
//					pr("val:"+val);
					if(val < min && val >= 0){
						pr("val: "+val);
						min = val;
						indexes = c;
					}
				}
			}
		}else{
			return -1;
//			min = 0;
		}
//		min += m[y][indexes[y]];
//		return min;
		if(min < Integer.MAX_VALUE)
			return min+m[y][indexes[y]];
		return Integer.MAX_VALUE;
	}

	static boolean isInSet(int[] set, int n){
		for(int i = 0; i < set.length; i++)
			if(set[i] == n)
				return true;
		return false;
	}
	
	
	static void goalIn(int[] distToGoals, int depth, Board b, GameState g, int[] block, boolean[][] p){
//		int[] player = g.getPlayerPos();
//		if(player[0] == block[0] && player[1] == block[1])
		if(block[0]<0 || block[1]<0)
			return;
		p[block[0]][block[1]]=false;

//		int[] distToGoals = new int[b.goals];
		for(int i = 0; i < distToGoals.length; i++){
			distToGoals[i] = depth;
		}

//		boolean[][] goals = b.goalArray.clone();
		boolean[][] goals = U.matrixClone(b.goalArray);


		ArrayList<DistNode> queue = new ArrayList<DistNode>();
		queue.add(new DistNode(block));
//		pr(p, block);
//		pr("");
		Move.findPathTo(distToGoals, queue, p, goals, b, g, depth, b.goals, b.goalOfPos);
//		pr(p);
//		pr("\n\n");
//		pr("dist");
//		pr(distToGoals);
	}



	 /*private static boolean iddps(final Board b, GameState gs, int depth, List<Move> solution, HashMap<GameState, Integer> seen, Move lastMove) {
        // Search limit reached
        if (depth == 0) {
            // U.pr("deep limit");
            return false;
        }
        // Goal state reached
        if (gs.isSolved(b)) {
            return true;
        }

        List<Move> moves = Move.findAllPossibleMoves(b, gs, lastMove);
        List<GameState> newStates = new ArrayList<GameState>();
        HashMap<GameState, Move> lookup = new HashMap<GameState, Move>();

        // U.prB(U.boardToFlatString(b, gs, false));

         for (int i = 0; i < moves.size(); i++) {
            Move action = moves.get(i);

			GameState tmpClone = new GameState(gs);
            GameState newState = tmpClone.doMove(b, action);

            // U.whatAmI_Move(action);

            Integer seenDepth = seen.get(newState);
            if (seenDepth == null || seenDepth < depth) {
                newStates.add(newState);
                lookup.put(newState, action);

                seen.put(newState, depth);
            }
        }

        // try {
            // System.in.read();
        // } catch (Exception e) {
        // }

        for (int i = 0; i < newStates.size(); i++) {
            GameState state = newStates.get(i);

            if(!testStop(depth, b, state)){
                boolean res = iddps(b, state, depth - 1, solution, seen, lookup.get(state));
                if (res == true) {
                    solution.add(0, lookup.get(state));
                    return true;
                }
            }
        }

        // Dead end
        return false;
    }*/

	static void pr(int[] m){
		for(int i = 0; i < m.length; i++){
			System.out.print(m[i]+"	");
		}
		System.out.println();
	}
	static void pr(int[][] m){
		for(int i = 0; i < m.length; i++){
			pr(m[i]);
		}
	}
	static void pr(boolean[] m){
		for(int i = 0; i < m.length; i++){
			System.out.print(m[i]?" ":"#");
		}
		System.out.println();
	}
	static void pr(boolean[][] m){
		for(int i = 0; i < m.length; i++){
			pr(m[i]);
		}
	}

	static void pr(boolean[] m, int p){
		for(int i = 0; i < m.length; i++){
			if(p==i){
				System.out.print("@");
			}else{
				System.out.print(m[i]?" ":"#");
			}
		}
		System.out.println();
	}
	static void pr(boolean[][] m, int[] p){
		for(int i = 0; i < m.length; i++){
			if(p[0]==i){
				pr(m[i], p[1]);
			}else{
				pr(m[i]);
			}
		}
	}
	static void pr(Object msg){
		System.out.println(""+msg);
	}
	 
}
